package database.tree;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.PrintStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import reference.DataFile;

import myutil.MyUtil;

public class BPlusTreeHelper implements Serializable {
	private static final long serialVersionUID = 1L;
	private Node root;

	public BPlusTreeHelper() {
		this.root = new Node(true, true);
	}

	public void addNode(String keyString, int rId) {
		Node insertedNode = lookupNode(keyString);
		Key key = new Key(keyString, rId);
		insertedNode.addKey(key);
		// split the leaf node
		if (insertedNode.isFull()) {
			splitNode(insertedNode);
		}
	}

	public void splitNode(Node node) {
		if (node.isRoot()) {
			createNewRoot(node);
		} else {
			if (node.getParent().getLastPointer() == node) {
				Key newKey = new Key();
				newKey.setNode(node);

				Node newLastPointer = new Node();
				newLastPointer.setParent(node.getParent());
				newLastPointer.setLeaf(node.isLeaf());

				Iterator<Map.Entry<String, Key>> it = node.getKeyMap().entrySet().iterator();
				int i = 0;
				while (it.hasNext()) {
					Map.Entry<String, Key> entry = it.next();
					Key key = entry.getValue();

					if (i >= MyUtil.MIN_NUMBER_KEY) {
						if (i == MyUtil.MIN_NUMBER_KEY) {
							newKey.setKeyString(key.getKeyString());
							newKey.setRecordId(key.getRecordId());
						}
						newLastPointer.addKey(key);
						it.remove();
					}

					i++;
				}

				node.getParent().addKey(newKey);
				node.getParent().setLastPointer(newLastPointer);
			} else {
				Key tempKey1 = new Key();
				tempKey1.setNode(new Node());
				tempKey1.getNode().setParent(node.getParent());
				tempKey1.getNode().setLeaf(node.isLeaf());

				Iterator<Map.Entry<String, Key>> it = node.getKeyMap().entrySet().iterator();
				int i = 0;
				while (it.hasNext()) {
					Map.Entry<String, Key> entry = it.next();
					Key key = entry.getValue();

					if (i >= MyUtil.MIN_NUMBER_KEY) {
						if (i == MyUtil.MIN_NUMBER_KEY) {
							tempKey1.setKeyString(key.getKeyString());
							tempKey1.setRecordId(key.getRecordId());
						}

						tempKey1.getNode().addKey(entry.getValue());
						it.remove();
					}
					i++;
				}
				node.getParent().addKey(tempKey1);

				List<Key> keyList = new ArrayList<Key>();
				List<Node> nodeList = new ArrayList<Node>();
				for (Map.Entry<String, Key> entry : node.getParent().getKeyMap().entrySet()) {
					keyList.add(entry.getValue());
					Node tempNode = entry.getValue().getNode();
					nodeList.add(tempNode);
				}

				Collections.sort(keyList);
				Collections.sort(nodeList);
				node.getParent().getKeyMap().clear();
				for (int j = 0; j < keyList.size(); j++) {
					keyList.get(j).setNode(nodeList.get(j));
					node.getParent().addKey(keyList.get(j));
				}

			}

			if (node.getParent().isFull()) {
				splitNode(node.getParent());
			}
		}
	}

	public void createNewRoot(Node oldRoot) {
		oldRoot.setRoot(false);
		Key newKey = new Key();
		newKey.setNode(oldRoot);

		root = new Node(false, true);
		oldRoot.setParent(root);
		// last point in new root
		Node newNode = new Node();
		newNode.setParent(root);
		newNode.setLeaf(oldRoot.isLeaf());
		root.setLastPointer(newNode);

		Iterator<Map.Entry<String, Key>> it = oldRoot.getKeyMap().entrySet().iterator();
		int i = 0;
		while (it.hasNext()) {
			Map.Entry<String, Key> entry = it.next();

			if (i >= MyUtil.MIN_NUMBER_KEY) {
				if (i == MyUtil.MIN_NUMBER_KEY) {
					newKey.setKeyString(entry.getKey());
					newKey.setRecordId(entry.getValue().getRecordId());
				}

				newNode.addKey(entry.getValue());
				it.remove();
			}
			i++;
		}
		root.addKey(newKey);
	}

	public void deleteKey() {

	}

	/*
	 * @return a leaf node that the new coming key should be
	 */
	public Node lookupNode(String keyString) {
		if (root.isLeaf()) {
			return root;
		} else {
			return recursiveLookup(root, keyString);
		}
	}

	/*
	 * Recursively search the B+tree on internal node return the hit leaf node
	 */
	private Node recursiveLookup(Node n, String keyString) {
		if (n.isLeaf())
			return n;
		// this map is sorted because we use TreeMap as implementation
		Map<String, Key> map = n.getKeyMap();
		Node rn = null;
		Key currentKey = null;
		for (Map.Entry<String, Key> item : map.entrySet()) {
			currentKey = item.getValue();

			if (keyString.compareTo(currentKey.getKeyString()) < 0) {
				rn = recursiveLookup(currentKey.getNode(), keyString);
			}
		}

		if (rn == null) {
			Node n1 = n.getLastPointer();
			if (n1 == null) {
				rn = recursiveLookup(currentKey.getNode(), keyString);
			} else {
				rn = recursiveLookup(n.getLastPointer(), keyString);
			}
		}

		return rn;
	}

	public String startPrint() {
		StringBuilder sb = new StringBuilder();
		for (Map.Entry<String, Key> item : this.root.getKeyMap().entrySet()) {
			if (this.root.isLeaf()) {
				sb.append(item.getValue().getKeyString() + " " + item.getValue().getRecordId()+"\n");
				// System.out.println(item.getValue().getKeyString() + "===>"
				// + item.getValue().getRecordId());
			} else {
				String subTree = printTree(item.getValue().getNode(), 1);
				
				sb.append( subTree + item.getValue().getKeyString() + "\n");
				//System.out.println(item.getValue().getKeyString());
			}
			// System.out.println("/////////////////////////////////");
		}
		if (root.getLastPointer() != null)
			sb.append(printTree(root.getLastPointer(), 1));

		return sb.toString();
	}

	public String printTree(Node node, int level) {
		StringBuilder sb = new StringBuilder();
		if (node.isLeaf()) {
			Iterator<Map.Entry<String, Key>> it = node.getKeyMap().entrySet().iterator();
			while (it.hasNext()) {
				Map.Entry<String, Key> entry = (Map.Entry<String, Key>) it.next();

				for (int i = 0; i < level; i++) {
					sb.append("\t");
				}
				sb.append(entry.getValue().getKeyString() + " " + entry.getValue().getRecordId() + "\n");
				// System.out.println(entry.getValue().getKeyString() + "===>"
				// + entry.getValue().getRecordId());
			}
		} else {
			Iterator<Map.Entry<String, Key>> it = node.getKeyMap().entrySet().iterator();

			while (it.hasNext()) {
				Map.Entry<String, Key> item = it.next();
				sb.append(printTree(item.getValue().getNode(), level + 1));
				String firstKey = item.getValue().getKeyString();
				for (int j = 0; j < level; j++) {
					sb.append("\t");
				}
				sb.append((firstKey)+ "\n");
			}
			if (node.getLastPointer() != null) {
				printTree(node.getLastPointer(), level + 1);
			}
		}

		return sb.toString();
	}

	// public getAllChildren(){
	//
	// }

	public Node getRoot() {
		return this.root;
	}

	public static void main(String[] args) {

//		PrintStream out;
//		try {
//			out = new PrintStream(new FileOutputStream("output.txt"));
//			System.setOut(out);
//		} catch (FileNotFoundException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}

		try {
			BPlusTreeHelper treeHelper = new BPlusTreeHelper();
			Map<String, String> testMap = new TreeMap<String, String>();
			FileInputStream fis = new FileInputStream(
					"/home/gassa/memcache_client/CSE562PRO1/movieVault.file");
			ObjectInputStream in = new ObjectInputStream(fis);
			DataFile dataFile = (DataFile) in.readObject();
			in.close();
			int i = 0;

			for (Map.Entry<Integer, Map<String, String>> item : dataFile.getAll().entrySet()) {
				treeHelper.addNode(item.getValue().get("Title"), item.getKey());
				testMap.put(item.getValue().get("Title"), String.valueOf(item.getKey()));
				i++;
			}
			System.out.println("=================>");
			System.out.println( treeHelper.startPrint() );
			System.out.println(testMap.size() + "//" + dataFile.getAll().size());
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} catch (ClassNotFoundException e) {
			e.printStackTrace();
		}
		//
		//
		// System.out.println("================>");
		// BPlusTreeHelper treeHelper = new BPlusTreeHelper();
		// Map<String, String> testMap = new TreeMap<String, String>();
		// for (int i = 0; i < 5000; i++) {
		// String keytemp = "test" + i;
		// treeHelper.addNode(keytemp, i);
		// testMap.put("test" + i, String.valueOf(i));
		// }
		//
		// treeHelper.startPrint();
		// System.exit(0);
	}
}
